二分查找算法 |
您所在的位置：网站首页 › java 二分查找算法 › 二分查找算法 |
二分查找算法
|
目录 1.二分查找算法的介绍 1.1算法思路 1.2算法模版 1.2.1查找区间左端点 1.2.1查找区间右端点 2.模版题 2.1数的范围 2.2数的三次方根 3.典题 3.1机器人跳跃问题 3.2分巧克力 4.课后题 1.二分查找算法的介绍 1.1算法思路假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。 说人话：就是把答案所在的区间逐渐缩小，直到区间内只有答案。 二分查找算法的时间复杂度是：logn（以2为底,以下同） 在不同数据范围下，由数据范围反推算法复杂度（做算法题时何时用二分）： 1.n≤1000 => O(n^2 logn) 2.nO(n logn) 我们还可以通过判断题目是否有单调性（本质上看的是二断性，单调性是二断性的体现），来判断是否适合用二分。是否可以使用二分法的关键在于：二分后，能否判断出答案所在的区间，而不是数据是否有序。 1.2算法模版 1.2.1查找区间左端点 public static int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) { r = mid } else { l = mid + 1; } } return l; }防溢出：int mid=l+(l+r)/2; 1.2.1查找区间右端点 public static int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) { l = mid } else { r = mid - 1; } } return l; }防溢出：int mid=l+(l+r+1)/2; 2.模版题 2.1数的范围题目： 给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。 对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 00 开始计数）。 如果数组中不存在该元素，则返回 -1 -1。 输入格式 第一行包含整数 n 和 q，表示数组长度和询问个数。 第二行包含 n 个整数（均在 1∼100001∼10000 范围内），表示完整数组。 接下来 q行，每行包含一个整数 k，表示一个询问元素。 输出格式 共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。 如果数组中不存在该元素，则返回 -1 -1。 数据范围 1≤n≤100000 1≤q≤10000 1≤k≤10000 一句话解析：先查找区间左端点，不存在直接返回（-1，-1），存在则继续查找区间右端点。 代码： import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int q = in.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = in.nextInt(); } int[] res = new int[2]; while (q-- > 0) { int x = in.nextInt(); int l = 0, r = n - 1; //先查找区间左端点 while (l < r) { int mid = l + r >> 1; if (arr[mid] >= x) { r = mid; } else { l = mid + 1; } } res[0] = l; //不存在直接返回（-1，-1） if (arr[l] != x) { System.out.println(-1 + " " + -1); } else { //存在则继续查找区间右端点 l = 0; r = n - 1; while (l < r) { int mid = l + r + 1 >> 1; if (arr[mid] 1e-8) { double mid = (l + r) / 2; if (mid * mid * mid >= x) { r = mid; } else { l = mid; } } System.out.printf("%.6f",l); } }注意： 1.要求保留 k位小数，EPS 就要取 1e^−(k+2)。 2.不能写成mid=l+r>>1,因为l和r都是浮点数。 3.因为是直接在区间找值，所以直接l=mid,r=mid; 3.典题 3.1机器人跳跃问题来自：今日头条2019 题目： 机器人正在玩一个古老的基于 DOS 的游戏。游戏中有 N+1座建筑从 0 到 N编号，从左到右排列。编号为 0的建筑高度为 0 个单位，编号为 i的建筑高度为 H(i)个单位。起初，机器人在编号为 0 的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第 k个建筑，且它现在的能量值是 E，下一步它将跳到第 k+1个建筑。如果 H(k+1)>E，那么机器人就失去 H(k+1)−E 的能量值，否则它将得到 E−H(k+1)的能量值。游戏目标是到达第 N 个建筑，在这个过程中能量值不能为负数个单位。现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？ 输入格式 第一行输入整数 N。 第二行是 N 个空格分隔的整数，H(1),H(2),…,H(N 代表建筑物的高度。 输出格式 输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。 数据范围 1≤N,H(i)≤10^5 分析： 1、由题意可知， 无论E比下一个H(i)大还是小，下一个E都等于2 * E - H（i），又H(i)≤10^5故 当E>=10^5时，一定可达所有建筑物。所以二分的范围在1到10^5。 2、当建筑物的高度一定时，随着初始的E的增加，到达建筑物的能量也增加，具有单调性。 3、check()函数表示，初始能量一定时是否能通过所有的建筑物，若能则返回true，否则返回false。 代码： import java.util.Scanner; public class Main { static int N = 100010, n; static int[] h = new int[N]; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); for (int i = 1; i > 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } System.out.println(l); } private static boolean check(int E) { for (int i = 1; i = 1e5) { return true; } } return true; } }
第八届蓝桥杯省赛Java A组/B组/C组 3.2分巧克力来自：第八届蓝桥杯省赛Java A组/B组/C组 题目: 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。 小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。 为了公平起见，小明需要从这 N 块巧克力中切出 K块巧克力分给小朋友们。 切出的巧克力需要满足： 形状是正方形，边长是整数大小相同例如一块 6×5 的巧克力可以切出 6 块 2×2的巧克力或者 2 块 3×3 的巧克力。 当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？ 输入格式 第一行包含两个整数 N 和 K。 以下 N 行每行包含两个整数 Hi 和 Wi。 输入保证每位小朋友至少能获得一块 1×1的巧克力。 输出格式 输出切出的正方形巧克力最大可能的边长。 数据范围 1≤N,K≤10^5 1≤Hi,Wi≤10^5 分析： 1.随着我们分出的小巧克力的边长越长，能分给的小朋友的数量就会越少（但每个小朋友得到的巧克力的面积就会越大），故这题显然是一个二分。 2.x表示我们分出的小巧克力的边长，很显然我们的目的是在区间1≤x≤max(Hi,Wi)内确定一个最大的边长x，使得第i块巧克力可以分成若干小块巧克力（注意不可拼接），所有巧克力的若干小块加起来的数量恰好等于k(小朋友的数量）。那么这个x就是我们最后的答案。 3.小巧克力边长 x 一定在 1 – 100000 之间答案即为：在 1 – 100000 之间找到一个最大的数，使得所有的 (w[i]/x) * (h[i]/x) 之和大于等于要求的数量 k。 代码： import java.util.Scanner; public class Main { static int N = 100010, n, k; static int[] h = new int[N]; static int[] w = new int[N]; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); k = in.nextInt(); for (int i = 0; i < n; i++) { h[i] = in.nextInt(); w[i] = in.nextInt(); } int l = 1, r = 100000; while (l < r) { int mid = l + r+1 >> 1; if (check(mid)) { l = mid; } else { r = mid - 1; } } System.out.println(l); } private static boolean check(int x) { int res = 0; for (int i = 0; i < n; i++) { res += (w[i] / x) * (h[i] / x); if (res >= k) { return true; } } return false; } } 4.课后题 704. 二分查找34. 在排序数组中查找元素的第一个和最后一个位置35. 搜索插入位置69. x 的平方根852. 山脉数组的峰顶索引162. 寻找峰值153. 寻找旋转排序数组中的最小值LCR 173. 点名 （原：剑指 offer：0～n-1 中缺失的数字 ）
以上为我个人的小分享，如有问题，欢迎讨论！！！ 都看到这了，不如关注一下，给个免费的赞
|
【本文地址】
今日新闻 |
推荐新闻 |